|
In cryptography, the Merkle–Damgård construction or Merkle–Damgård hash function is a method of building collision-resistant cryptographic hash functions from collision-resistant one-way compression functions.〔Goldwasser, S. and Bellare, M. ("Lecture Notes on Cryptography" ). Summer course on cryptography, MIT, 1996-2001〕 This construction was used in the design of many popular hash algorithms such as MD5, SHA1 and SHA2. The Merkle–Damgård construction was described in Ralph Merkle's Ph.D. thesis in 1979.〔R.C. Merkle. (''Secrecy, authentication, and public key systems.'' ) Stanford Ph.D. thesis 1979, pages 13-15.〕 Ralph Merkle and Ivan Damgård independently proved that the structure is sound: that is, if an appropriate padding scheme is used and the compression function is collision-resistant, then the hash function will also be collision resistant.〔R.C. Merkle. ''A Certified Digital Signature''. In Advances in Cryptology - CRYPTO '89 Proceedings, Lecture Notes in Computer Science Vol. 435, G. Brassard, ed, Springer-Verlag, 1989, pp. 218-238.〕〔I. Damgård. ''A Design Principle for Hash Functions''. In Advances in Cryptology - CRYPTO '89 Proceedings, Lecture Notes in Computer Science Vol. 435, G. Brassard, ed, Springer-Verlag, 1989, pp. 416-427.〕 The Merkle–Damgård hash function first applies an MD-compliant padding function to create an input whose size is a multiple of a fixed number (e.g. 512 or 1024) — this is because compression functions cannot handle inputs of arbitrary size. The hash function then breaks the result into blocks of fixed size, and processes them one at a time with the compression function, each time combining a block of the input with the output of the previous round.〔 In order to make the construction secure, Merkle and Damgård proposed that messages be padded with a padding that encodes the length of the original message. This is called ''length padding'' or Merkle–Damgård strengthening. In the diagram, the one-way compression function is denoted by ''f'', and transforms two fixed length inputs to an output of the same size as one of the inputs. The algorithm starts with an initial value, the initialization vector (IV). The IV is a fixed value (algorithm or implementation specific). For each message block, the compression (or compacting) function ''f'' takes the result so far, combines it with the message block, and produces an intermediate result. The last block is padded with zeros as needed and bits representing the length of the entire message are appended. (See below for a detailed length padding example.) To harden the hash further the last result is then sometimes fed through a ''finalisation function''. The finalisation function can have several purposes such as compressing a bigger internal state (the last result) into a smaller output hash size or to guarantee a better mixing and avalanche effect on the bits in the hash sum. The finalisation function is often built by using the compression function (Note that in some documents instead the act of length padding is called "finalisation"). == Security characteristics == The popularity of this construction is due to the fact, proven by Merkle and Damgård, that if the one-way compression function ''f'' is collision resistant, then so is the hash function constructed using it. Unfortunately, this construction also has several undesirable properties: * Length extension — once an attacker has one collision, he can find more very cheaply. * Second preimage attacks against long messages are always much more efficient than brute force. * Multicollisions (many messages with the same hash) can be found with only a little more work than collisions.〔Antoine Joux. ''Multicollisions in iterated hash functions. Application to cascaded construction.'' In Advances in Cryptology - CRYPTO '04 Proceedings, Lecture Notes in Computer Science, Vol. 3152, M. Franklin, ed, Springer-Verlag, 2004, pp. 306–316.〕 * "Herding attacks" (first committing to an output h, then mapping messages with arbitrary starting values to h) are possible for more work than finding a collision, but much less than would be expected to do this for a random oracle.〔John Kelsey and Tadayoshi Kohno. ''Herding Hash Functions and the Nostradamus Attack'' In Eurocrypt 2006, Lecture Notes in Computer Science, Vol. 4004, pp. 183–200.〕 * "Extension attacks": Given the hash ''H(X)'' of an unknown input ''X'', it is easy to find the value of ''H(pad(X) || Y)'', where ''pad'' is the padding function of the hash. That is, it is possible to find hashes of inputs related to ''X'' even though ''X'' remains unknown.〔Yevgeniy Dodis, Thomas Ristenpart, Thomas Shrimpton. ''Salvaging Merkle–Damgård for Practical Applications''. Preliminary version in Advances in Cryptology - EUROCRYPT '09 Proceedings, Lecture Notes in Computer Science Vol. 5479, A. Joux, ed, Springer-Verlag, 2009, pp. 371–388.〕 A random oracle would not have this property, and this may lead to simple attacks even for ''natural'' schemes proven secure in the random oracle model.〔J.S. Coron, Y. Dodis, C. Malinaud, and P. Puniya. ''Merkle–Damgård Revisited: How to Construct a Hash Function.'' Advances in Cryptology – CRYPTO '05 Proceedings, Lecture Notes in Computer Science, Vol. 3621, Springer-Verlag, 2005, pp. 21–39.〕 Length extension attack was actually used to attack a number of commercial web message authentication schemes such as one used by Flickr.〔Thai Duong, Juliano Rizzo, (Flickr's API Signature Forgery Vulnerability ), 2009〕 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「Merkle–Damgård construction」の詳細全文を読む スポンサード リンク
|